package com.hatricks.is.base.sort;

import java.util.Arrays;

/**
 * @packageName: com.hatricks.base.sort
 * @className: MergeSort
 * @author: yanyuhui yanyuhui@chinasofti.com
 * @date: 2022/6/10 15:07
 * @description: 归并排序
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        MergeSort.mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr, int left, int right, int[] tempArr) {
        if (left < right) {
            int mid = (left + right) >> 1;
            mergeSort(arr, left, mid, tempArr);
            mergeSort(arr, mid + 1, right, tempArr);
            sort(arr, left, mid, right, tempArr);
        }
    }

    private static void sort(int[] array, int left, int mid, int right, int[] tempArray) {
        int i = left;//初始化i，左边有序子数组的初始索引
        int j = mid + 1;//初始化j，右边有序子数组的初始索引
        int index = 0;//用于标识tempArray数组当前所在的下标
        //(一)
        //先把左右两边(有序)的子数组按照规则填充到tempArray数组
        //直到左右两边的有序子数组，有一边处理完毕为止
        while (i <= mid && j <= right) {//当左右子数组都没完成数据转移时
            if (array[i] <= array[j]) {//左边的元素小于右边的元素，将该元素加入到临时数组中,
                // 一直循环直到找到一个元素比右边的大，将转移权交给右边的子数组
                tempArray[index] = array[i];
                i++;//向右移动一位
            } else {//右边的元素小于左边的元素，将该元素加入到临时数组中,
                // 一直循环直到找到一个元素比左边的大，将转移权交给左边的子数组
                tempArray[index] = array[j];
                j++;//向右移动一位
            }
            index++;
        }
        //(二)
        //把有剩余数据的一边的数据依次全部填充到temp
        while (i <= mid) {//说明左边的子数组有剩余元素
            tempArray[index] = array[i];
            i++;
            index++;
        }
        while (j <= right) {//说明右边的子数组有剩余元素
            tempArray[index] = array[j];
            j++;
            index++;
        }

        //(三)
        //将tempArray数组的元素拷贝到array
        // 注意，并不是每次都是拷贝所有元素到array（待排序）数组中
        // 第一次合并tempLeft = 0 , right = 1
        // 第二次合并tempLeft= 2 right = 3
        // 第三次合并 tempLeft=0 right = 3
        // 最后一次tempLeft= 0 right = 7
        index = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            array[tempLeft] = tempArray[index];
            index++;
            tempLeft++;
        }
    }
}

